package map.dijkstra;

import java.util.*;

class Edge{
    int to; //邻接节点
    int val; //边权值

    public Edge(int to, int val) {
        this.to = to;
        this.val = val;
    }
}
class Pair<U, V>{
    public final U first;
    public final V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}
public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<List<Edge>> grid = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            grid.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int k = scanner.nextInt();
            grid.get(x).add(new Edge(y, k));
        }
        int start = 1;
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;
        boolean[] isVisited = new boolean[n + 1];
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.second, o2.second));
        pq.add(new Pair<>(start, 0));
        while (!pq.isEmpty()) {
            Pair<Integer, Integer> cur = pq.poll();
            if (isVisited[cur.first]) {
                continue;
            }
            isVisited[cur.first] = true;
            for (Edge edge : grid.get(cur.first)) {
                if (!isVisited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) {
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<>(edge.to, minDist[edge.to]));
                }
            }
        }
        if (minDist[n] == Integer.MAX_VALUE) {
            System.out.println(-1); // 不能到达终点
        } else {
            System.out.println(minDist[n]); // 到达终点最短路径
        }
    }
}
